#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <Vector.hpp>

using namespace std;
class Solution
{
    vector<pair<int, int>> neighboars = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

public:
    void solve(vector<vector<char>> &board)
    {
        for (int x = 0; x < board[0].size(); x++)
        {
            if (board[0][x] == 'O')
            {
                floorFill(board, x, 0, 'T');
            }
            if (board[board.size() - 1][x] == 'O')
            {
                floorFill(board, x, board.size() - 1, 'T');
            }
        }
        for (int y = 1; y < board.size(); y++)
        {
            if (board[y][0] == 'O')
            {
                floorFill(board, 0, y, 'T');
            }
            if (board[y][board[0].size() - 1] == 'O')
            {
                floorFill(board, board[0].size() - 1, y, 'T');
            }
        }
        for (int x = 0; x < board[0].size(); x++)
        {
            for (int y = 0; y < board.size(); y++)
            {
                if (board[y][x] == 'T')
                {
                    board[y][x] = 'O';
                }
                else if (board[y][x] == 'O')
                {
                    board[y][x] = 'X';
                }
            }
        }
    }
    void floorFill(vector<vector<char>> &grid, int x, int y, int id)
    {
        if (x >= 0 && x < grid[0].size() && y >= 0 && y < grid.size() && grid[y][x] == 'O')
        {
            grid[y][x] = id;
            for (int i = 0; i < 4; i++)
            {
                int newX = x + neighboars[i].first;
                int newY = y + neighboars[i].second;
                floorFill(grid, newX, newY, id);
            }
        }
    }
};
int main()
{
    cout << "Code130" << endl;
    Solution s;
    vector<vector<char>> board = {
        {'X', 'X', 'O'},
        {'X', 'X', 'O'},
        {'X', 'O', 'O'},
        {'O', 'X', 'X'}};
    s.solve(board);
    Print2DVector(board);
    return 0;
}

/*
overtime
class Solution
{
    vector<pair<int, int>> neighboars = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

public:
    void solve(vector<vector<char>> &board)
    {
        for (int x = 0; x < board[0].size(); x++)
        {
            for (int y = 0; y < board.size(); y++)
            {
                if (board[y][x] == 'O')
                {
                    floorFill(board, x, y, 'T');
                }
            }
        }
        for (int x = 0; x < board[0].size(); x++)
        {
            for (int y = 0; y < board.size(); y++)
            {
                if (board[y][x] == 'T')
                {
                    board[y][x] = 'O';
                }
            }
        }
    }
    void floorFill(vector<vector<char>> &grid, int x, int y, int id)
    {
        set<pair<int, int>> visited;
        queue<pair<int, int>> waited;
        bool hasReachedBoard = false;
        waited.push({x, y});
        while (!waited.empty())
        {
            grid[waited.front().second][waited.front().first] = id;
            visited.insert(waited.front());
            for (int i = 0; i < 4; i++)
            {
                int newX = waited.front().first + neighboars[i].first;
                int newY = waited.front().second + neighboars[i].second;
                if (newX >= 0 && newX < grid[0].size() && newY >= 0 && newY < grid.size())
                {
                    if (grid[newY][newX] == 'O')
                    {
                        if (visited.count({newX, newY}) == 0)
                        {
                            waited.push({newX, newY});
                        }
                    }
                }
                else
                {
                    hasReachedBoard = true;
                }
            }
            waited.pop();
        }
        if (!hasReachedBoard)
        {
            for (auto coord : visited)
            {
                grid[coord.second][coord.first] = 'X';
            }
        }
    }
};
*/